In printers that employ laser engines as the "print mechanism", data must be provided at a speed that is fast enough to keep up with the print action (which can be measured by the rate of movement of the paper past the imaging drum). In such printers, formatting is either performed on the host computer, with large volumes of rasterized image data shipped to the printer at high speed, or on a formatter within the printer itself. Since a conventional laser printer engine operates at a constant speed, if rasterized image data is not available when a previous segment of image data has been imprinted, a "print overrun" occurs and the page is not printable.
Several methods have been used in the prior art to avoid print overruns. First, a full raster bit map of an entire page may be stored in the printer so that the print mechanism always has rasterized data awaiting printing. However, this solution requires large amounts of random access memory (RAM) for each page. A second method for assuring the availability of print data to a laser printer is to construct a display list from the commands describing a page. During formatting, a page description received from a host is converted into a series of simple commands, called display commands, that describe what must be printed. The display commands are parsed and sorted according to their vertical position on the page. The page is then logically divided into sections called page strips, which page strips are then individually rendered into a raster bit map and passed to the print engine for printing. This procedure enables lesser amounts of RAM to be used for the print image.
When the display commands are rendered at a fast enough pace, the same memory used to store a first page strip can be reused for a subsequent page strip further down the page. For example, in certain prior art printers it is known to employ three raster buffers for storing page strips. During page processing, the first buffer is reused for a fourth strip on the page, the second is reused for a fifth strip, etc. However, under standard (generally maximum) page-per-minute performance, little time is left between finishing printing of a strip and when a next strip is required to be rasterized from the same print buffer.
Under certain circumstances, "complex" page strips will include many display commands and require a longer than normal time for rasterization. Additionally, to rasterize a page strip (whether "complex" or not), more memory space may be required than is currently available--depending upon several factors associated with the printer, including memory size, job to be printed, and other printer system activities. In the case of a complex strip, rasterization time may increase to such an extent that the succeeding strip can not be delivered on time, thus causing a print overrun to occur. In the case of insufficient memory space being allocable for a strip, a print overrun will also occur.
In the event of low available memory for processing print commands, each page strip of a page may be reevaluated and passed through several steps in attempt to reduce memory allocation requirements and free up more memory. For example, each page strip may be rasterized and compressed using one of several compression techniques. U.S. Pat. No. 5,479,587 describes a Page Printer Having Adaptive Data Compression for Memory Minimization and is incorporated herein by reference in full. After a page strip is rasterized and compressed, the memory allocation requirement for that strip is determined. If the memory allocation requirement is less than the memory allocation requirement of the display list for that same strip (relative to a predetermined comparison threshold), then the rasterized and compressed version will be used and stored in memory rather than the display list. On the other hand, if the rasterized and compressed strip's memory allocation requirement is not less than the memory allocation requirement for its display list (per the threshold), then the strip may be processed again using a different compression technique. These steps of rasterizing a strip, compressing it, comparing the size of the compressed version to the display list, and determining if the memory allocation requirement of the compressed version is less than that of the display list, may be repeated multiple times using differing compression techniques and/or thresholds until the strip's allocation requirement is less than that of its display list.
When it is determined that the threshold has been met (i.e., the rasterized and compressed page strip memory allocation requirement is less than that of the display list), then the strip's display list is deallocated from memory and the rasterized and compressed page strip is stored to memory. The page strip is stored in memory by being dissected into fragments (segments) and then linked and distributed into "holes" in the memory. The "holes" are, typically, smaller isolated free areas of memory surrounded by larger unavailable (used) areas.
Once all of the page strips have been rasterized, compressed, evaluated and distributed (when the threshold was met) then processing of the print commands resumes at the point where the event of low available memory was previously detected (i.e., the point that initiated the reevaluation process for the page). The page strip that was previously attempting a memory allocation (but detected the low available memory event) should now have a better chance of being able to satisfy its memory allocation.
Although these page strip processing techniques often enable a page strip memory allocation request to be satisfied, fragmentation of the memory may not be reduced. Fragmentation may not be reduced because each strip is processed independently of all other strips. For example, if a first strip is rasterized, distributed and stored, and then some memory surrounding a distributed segment of that first strip is subsequently deallocated, then the first strip ends up actually causing fragmentation in the memory since it remains there even after its surrounding areas were deallocated. This scenario may occur, for example, if a segment of the first strip was stored in a hole that was created by a second strip's display list, and then the second strip's display list was removed from around the first strip in order to render the second strip's rasterized and compressed page strip. Disadvantageously, if the memory becomes too fragmented (i.e., too many "holes" exist) such that other memory allocation requests cannot be satisfied that require contiguous allocations of memory, then overall page processing is crippled and a print overrun may result.
Accordingly, an object of the present invention is to reduce memory fragmentation in a page printer memory.